package subarraySum

var ans int

/*
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
*/
// 一开始想着用回溯法，发现nums中的数字可以为负数，所以不能保证累加的和是具有严格单调性的
// 由于子数组是连续的
/*
假设从下标x,到下标y的子数组和为k，记为count[y-x]  y>=x>=0
count[y]=count[y-0]=count[y-1] + nums[y],为从0开始到下标y的数字累加和
则count[y-x] = count[y] - count[x-1]  （错位相减得到）
即count[x-1] = count[y] - k
我们用map的key来存储count[x]的值，value来存储count[x]出现的次数
只需要判断count[y] - k 是否存在于map中，存在则表明：
存在0<=x<=y，使得count[x-1] = count[y] - k，value为子数组的和为k的个数
count[y]遍历一遍nums数组，就能获得所有的值
*/
func subarraySum(nums []int, k int) int {
	if len(nums) == 1 && nums[0] == k {
		return 1
	}
	var count int
	mp := make(map[int]int)
	// 初始化
	mp[0] = 1
	for i := 0; i < len(nums); i++ {
		count += nums[i]
		if _, ok := mp[count-k]; ok {
			ans += mp[count-k]
		}
		mp[count]++
	}
	return ans
}
